Các sự kiện sớm nhất của lịch sử Bắc Kinh xuất hiện trong các câu truyện truyền thuyết và huyền thoại. Trong quyển đầu tiên của "Sử ký"- "Ngũ đế bản kỷ", Tư Mã Thiên viết về chiến thắng của Hoàng Đế trước Viêm Đế trong trận Phản Tuyền vào thế kỷ XXVI TCN, trận chiến có thể diễn ra gần các thôn Thượng Phản Tuyền và Hạ Phản Tuyền thuộc huyện Diên Khánh ở tây bắc Bắc Kinh.[21][Note 1] Kết quả là hai bộ lạc của Viêm Đế và Hoàng Đế thống nhất, khởi đầu tộc Hoa Hạ hay Viêm Hoàng tử tôn. Bộ lạc của Hoàng Đế sau đó đánh bại bộ lạc Cửu Lê của Xi Vưu trong trận Trác Lộc, có thể diễn ra tại Trác Lộc, cách Diên Khánh 75 km về phía tây và thuộc địa phận tỉnh Hà Bắc.[21][22]

Hoàng Đế được cho là lập ra khu định cư U Lăng (幽陵) tại hoặc gần Trác Lộc.[22] Một hậu duệ của Hoàng Đế là Nghiêu cho thành lập một đô thị là U Đô (幽都) tại khu vực Hà Bắc-Bắc Kinh khoảng 4.000 năm trước.[22] U (幽) hay U châu (幽州) sau đó trở thành một trong các tên gọi lịch sử của Bắc Kinh. Ở Ngư Tử Sơn thuộc thôn Sơn Đông Trang của huyện Bình Cốc, có một trong vài di tích được cho là lăng mộ của Hoàng Đế. Mặc dù Hoàng Đế lăng ở tỉnh Thiểm Tây nổi tiếng hơn, song một nghiên cứu của Viện Khoa học Xã hội Bắc Kinh và Bảo tàng Quốc gia Trung Quốc vào năm 1992 đưa ra kết luận rằng Ngư Tử Sơn có khả năng là nơi có lăng mộ "thực sự" của Hoàng Đế.[21] Mối liên hệ của Ngư Tử Sơn với Hoàng Đế có thể truy nguyên từ thời nhà Đường, khi các thi nhân Trần Tử Ngang và Lý Bạch đề cập đến lăng mộ Hoàng Đế trong các bài thơ của họ về U châu.[23]

Sự kiện đầu tiên trong lịch sử Bắc Kinh có các bằng chứng khảo cổ xác nhận diễn ra vào thế kỷ XI TCN, khi nước Chu chinh phục nhà Thương. Theo Tư Mã Thiên, Chu Vũ Vương vào năm cai trị thứ 11 của mình lật đổ Trụ Vương của nhà Thương, sau đó phong tước cho các quý tộc trong các lãnh địa của mình, bao gồm quân chủ nước Kế và nước Yên.[24] Theo Khổng Tử, Chu Vũ Vương rất muốn thiết lập địa vị hợp pháp của mình sau chiến thắng trước nhà Thương, chưa kịp hạ xa đã phong hậu duệ của Hoàng Đế làm người cai trị nước Kế.[25] Sau đó, Chu Vũ Vương cho một người trong họ là Cơ Thích làm vua chư hầu nước Yên, song Cơ Thích còn vướng bận các vấn đề khác nên phái trưởng tử của mình là Cơ Khắc đi cai quản đất thụ phong. Cơ Khắc được xem là quân chủ khai quốc của nước Yên. Do niên đại các sự kiện lịch sử trong Sử ký trước năm 841 TCN không thể xác định rạch ròi theo lịch Gregory, chính quyền Bắc Kinh sử dụng mốc 1042 TCN làm niên đại ước lượng chính thức cho sự kiện này.[26]

Kế thành (蓟城) được cho là nằm ở phần tây nam khu vực đô thị của Bắc Kinh hiện nay, ngay phía nam của Quảng An Môn thuộc các khu Tây Thành và Phong Đài.[27] Một vài thư tịch lịch sử đề cập đến một "Kế Sơn" ở tây bắc thành phố, có thể tương ứng với một gò lớn tại Bạch Vân Quán, bên ngoài Tây Tiện Môn và cách khoảng 4 km (2,5 mi) về phía bắc Quảng An Môn.[28]

Đô thành nước Yên nằm ở phía nam Kế thành, nay thuộc thôn Đổng Gia Lâm của trấn Lưu Ly Hà thuộc quận Phòng Sơn, bên trong tường thành là một khu dân cư lớn và khai quật được trên 200 mộ quý tộc.[29] Trong số các hiện vật quan trọng nhất từ di chỉ Lưu Ly Hà, có "Cận đỉnh" ba chân làm bằng đồng thiếc, có khắc dòng chữ kể về hành trình của Cận- người được Yên hầu Khắc phái vận chuyển đồ ăn thức uống cho cha là Triệu công Thích ở đô thành Hạo Kinh của triều Chu.[30] Triệu công cảm động và trao cho Cận tiền vỏ ốc để trả cho việc chế tác một chiếc đỉnh nhằm ghi nhớ sự kiện này. Dòng chữ do đó xác nhận việc Chu Vương bổ nhiệm thân thích làm vua nước Yên và vị trí của đô thành nước Yên.

Cả hai nước Yên và Kế đều nằm trên một tuyến đường mậu dịch bắc-nam quan trọng, từ Trung Nguyên dọc theo sườn đông của Thái Hành Sơn để đến các vùng thảo nguyên phương Bắc. Nước Kế nằm ở ngay phía bắc Vĩnh Định Hà, là một điểm dừng chân thuận lợi của các thương đoàn. Ở đây, các tuyến đường đi về phía tây bắc qua các con đèo tách biệt với các tuyến đường đi về đông bắc. Nước Kế cũng có một nguồn cung cấp nước ổn định từ Liên Hoa Trì, hồ này nay vẫn tồn tại và nằm ở phía nam ga Bắc Kinh Tây. Cố đô nước Yên dựa vào nguồn nước từ Lưu Ly Hà.

Vào thời Tây Chu hoặc đầu thời Đông Chu, nước Yên chinh phục nước Kế và chuyển quốc đô đến Kế thành, Kế thành không bị đổi tên cho đến thế kỷ II CN.[27] Do có mối quan hệ lịch sử với nước Yên, thành Bắc Kinh thường cũng được gọi là Yên Kinh (燕京).[Note 2][27][31][32][33]

Nước Yên tiếp tục khuếch trương lãnh thổ và trở thành một trong Chiến Quốc thất hùng.[34] Lãnh thổ nước Yên trải dài từ Hoàng Hà đến Áp Lục Giang.[35] Nước Yên phải đối mặt với mối đe dọa từ các sắc dân du mục trên thảo nguyên, vì thế nước này cho xây dựng công sự có tường bao quanh ở biên giới phía bắc. Dấu vết của Yên Trường Thành tại huyện Xương Bình có niên đại từ năm 283 TCN.[36]

Năm 226 TCN, Kế thành thất thủ trước cuộc xâm lược của nước Tần, nước Yên buộc phải rời đô đến Liêu Đông.[37] Nước Tần tiêu diệt hoàn toàn nước Yên vào năm 222 TCN. Năm sau đó, khi hoàn thành thống nhất Trung Hoa, quốc quân nước Tần xưng là Tần Thủy Hoàng.